package 链表.环形链表;

public class Josefu {
    public static void main(String[] args) {
        CircleLinkedList circleLinkedList = new CircleLinkedList();
        circleLinkedList.addBoy(5);
        circleLinkedList.list();

        System.out.println("~~~~~~~~");
        circleLinkedList.out(1,2,5);
    }
}

class CircleLinkedList{
    public Boy first = null;

    public void addBoy(int nums){ // nums添加1-10共10个小孩组成一个环

        // 由于first指针作为最后一个孩子最终仍指回first构成环，故不能移动first指针，由此定义出第二个指针
        Boy temp = null;
        // 特殊情况判断
        if (nums <1) {
            System.out.println("请传入的nums大于1");
            return;
        }
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) { // 由于temp和first都指向空，建立连接
               first = boy;
               first.setNext(first);
               temp = first;
               continue;
            }
            temp.setNext(boy);
            boy.setNext(first);

            temp = boy; // temp每回合后移
        }
    }

    // 打印环形链表
    public void list(){
        if (first.getNext() == null) {
            System.out.println("一个小孩都没有");
        }
        Boy temp = first;
        while (true) {
            System.out.println(temp);
            if (temp.getNext() == first) {
                break;
            }
            temp = temp.getNext();
        }
    }

    /**
     * 从第startNo个小孩开始报数，每报到countOut个小孩时，该小孩出圈，从下一个小孩继续报数，直到小孩都出圈。
     * @param startNo 从第几个小孩开始报数
     * @param countOut 报几次数即出圈
     * @param boyTotal 小孩总数
     */
    public void out(int startNo,int countOut,int boyTotal){
        if (startNo < 1 || first == null || countOut > boyTotal) {
            System.out.println("参数输入有误");
            return;
        }
        // 指向当前小孩的前一个孩子的辅助指针
        Boy frontPoint = first;
        while (true) {
            if (frontPoint.getNext() == first) {
                break;
            }
            frontPoint = frontPoint.getNext();
        }
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            frontPoint = frontPoint.getNext();
        }
        while (true) {
            if (first == frontPoint) {
                break;
            }
            for (int i = 0; i < countOut - 1; i++) {
                frontPoint = frontPoint.getNext();
                first = first.getNext();
            }
            System.out.printf("编号为%d的小孩出圈！\n",first.getNo());
            first = first.getNext();
            frontPoint.setNext(first);
        }
        System.out.println("最终留在圈中的小孩是"+first);
    }
}

class Boy{
    private int no;
    private Boy next;

    public Boy(int no){
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public int getNo(){
        return no;
    }

    public void setNext(Boy next){
        this.next = next;
    }

    public void setNo(int no){
        this.no = no;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}